#include<iostream>
using namespace std;
#include<vector>
#include<unordered_set>
#include<queue>
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n + 1);
        dp[1] = 1;
        for (int i = 2, i2 = 1, i3 = 1, i5 = 1; i <= n; ++i) {
            if (dp[i - 1] == dp[i3] * 3)
                ++i3;
            if (dp[i - 1] == dp[i5] * 5)
                ++i5;
            int a = dp[i2] * 2, b = dp[i3] * 3, c = dp[i5] * 5;
            if (a <= b && a <= c)
                dp[i] = dp[i2++] * 2;
            else if (b <= a && b <= c)
                dp[i] = dp[i3++] * 3;
            else
                dp[i] = dp[i5++] * 5;
        }
        return dp[n];
    }
};
int main() {
    Solution().nthUglyNumber(10);
}